﻿namespace Leetcode.N0307.V1;

public class NumArray
{

    private INumArray numArraySize;
    public NumArray(int[] nums)
    {
        this.numArraySize = new NormalArray(nums);
        var length = nums.Length / NumArraySize.SIZE_STEP;
        while (length > 0)
        {
            this.numArraySize = new NumArraySize(this.numArraySize);
            length = length / NumArraySize.SIZE_STEP;
        }
    }

    public void Update(int index, int val)
    {
        this.numArraySize.Update(index, val);
    }

    public int SumRange(int left, int right)
    {
        return this.numArraySize.SumRange(left, right);
    }
}

public class NumArraySize : INumArray
{

    public const int SIZE_STEP = 2;
    private readonly int[] nums;
    private readonly INumArray next;
    private readonly int size;

    public NumArraySize(INumArray next)
    {
        var nums = next.Nums;
        if (nums.Length % SIZE_STEP == 0)
        {
            this.nums = new int[nums.Length / SIZE_STEP];
        }
        else
        {
            this.nums = new int[nums.Length / SIZE_STEP + 1];
        }

        for (int i = 0; i < nums.Length; i++)
        {
            this.nums[i / SIZE_STEP] += nums[i];
        }

        this.next = next;
        this.size = next.Size * SIZE_STEP;

    }

    public int[] Nums => this.nums;
    public int Size => this.size;

    public int Update(int index, int val)
    {
        var d = this.next.Update(index, val);
        this.nums[index / this.size] += d;
        return d;
    }

    public int SumRange(int left, int right)
    {
        var leftBlock = left / this.size;
        var rightBlock = right / this.size;
        var sum = 0;

        var mLeft = left % this.size;
        if (mLeft > 0)
        {
            if (leftBlock == rightBlock)
            {
                return this.next.SumRange(left, right);
            }
            sum += this.next.SumRange(left, left + this.size - mLeft - 1);
            leftBlock++;
        }

        var mRight = (right + 1) % this.size;
        if (mRight > 0)
        {
            if (leftBlock == rightBlock)
            {
                return this.next.SumRange(left, right);
            }

            sum += this.next.SumRange((right + 1) - mRight, right);
            rightBlock--;
        }

        for (int i = leftBlock; i <= rightBlock; i++)
        {
            sum += this.nums[i];
        }

        return sum;
    }
}


public interface INumArray
{
    int[] Nums { get; }
    int Size { get; }
    int Update(int index, int val);
    int SumRange(int left, int right);
}

public class NormalArray : INumArray
{
    private int[] nums;

    public int[] Nums => this.nums;
    public int Size => 1;

    public NormalArray(int[] nums)
    {
        this.nums = nums;
    }

    public int Update(int index, int val)
    {
        var d = val - this.nums[index];
        this.nums[index] = val;
        return d;
    }

    public int SumRange(int left, int right)
    {
        var sum = 0;
        for (int i = left; i <= right; i++)
        {
            sum += this.nums[i];
        }
        return sum;
    }
}
